package com.wz.leetcode.stackandqueue;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class LargestRectangle_84 {
    public static int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(right, n);

        // 单调栈栈顶最大
        Deque<Integer> monoStack = new LinkedList<>();
        for (int i = 0; i < n; ++i) {
            while (!monoStack.isEmpty() && heights[monoStack.peek()] >= heights[i]) {
                right[monoStack.peek()] = i;
                monoStack.pop();
            }
            left[i] = (monoStack.isEmpty() ? -1 : monoStack.peek());
            monoStack.push(i);
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int tmp = (right[i] - left[i] - 1) * heights[i];
            System.out.println("a[" + i + "] = " + tmp);
            ans = Math.max(ans, tmp);
        }
        return ans;
    }

    public static void main(String[] args) {
        /**
         * a[0] = 2
         * a[1] = 8
         * a[2] = 5
         * a[3] = 10
         * a[4] = 15
         * a[5] = 20
         * a[6] = 12
         * a[7] = 3
         * 20
         */
        System.out.println(largestRectangleArea(new int[]{2, 1, 5, 5, 5, 5, 2, 3}));
    }
}
